1. Field of the Invention
The present invention relates to a method and apparatus for hierarchically approximating shape data with an image, in which the data amount is reduced by reducing the complexity of the shape of a geometric model which is used in generating CG (Computer Graphics), thereby enabling the CG to be drawn at a high speed. The invention also relates to a method and apparatus for hierarchically approximating shape data with an image, which is suitable for use in a game using CG, VR (Virtual Reality), designing, and the like since a shape which was approximated so as not to give a sense of incongruity is changed.
2. Description of the Prior Art
When drawing using a model as part of computer graphics, the same model may be used repeatedly. For example, as shown in FIG. 14, a detailed original model having data of 100% is formed and the CG is drawn on a display by using it repeatedly. When the model is arranged in a far position in a picture plane and is rendered smaller, the same model still is used, and the degree of details of the model is not changed. Therefore, the time required for the drawing depends on the degree of detail of the model and the number of models.
However, when the observer pays no attention to the model because the model is minimized and looks smaller on the picture plane or the model is out of a target point of the picture plane, it is not always necessary to draw by using the model having a high degree of detail. That is, by using a similar model in which a degree of detail is decreased to a certain extent by using a method of reducing the number of vertices of the model, reducing the number of planes of a polygon, or the like, it. can appear as if the same model is used. FIG. 15 shows such an example. When the model is to appear at a distance and its size on the picture plane is small, as shown in the example, it is sufficient to draw the CG by using models in which data is reduced to, for example, 50% or 25% from that of the original model and for which the degree of detail is reduced. By using a model having a data amount smaller than that of the original model as mentioned above, a high drawing speed can be realized.
Such an approximation of the model is useful for the drawing of the CG display as mentioned above. However, if the data amount of the model is simply reduced by approximating the details of the model, the observer feels incongruity when he sees the approximated model. If this sense of incongruity can be suppressed, requests for both of the drawing speed and the drawing quality can be satisfied. For this purpose, it is desirable to reduce the data amount in a manner such that a general characteristic portion of the model is left and the other portions are reduced. Hitherto, such an approximation of the model is often executed by the manual work of a designer, so that much expense and time are necessary for the above work.
A method of obtaining a more real image by adhering a two-dimensional image to a plane of a model as a drawing target is generally used. This is called a texture mapping. The image which is adhered in this instance is called a texture. When the approximation of the shape as mentioned above is executed to the model which was subjected to the texture mapping, it is necessary to also pay attention to the texture adhered to the model plane. That is, it is necessary to prevent a deterioration in the appearance of the model due to a deformation of the texture shape at the time of approximation and to prevent the occurrence of a problem such that the amount of work is increased since the texture must be again adhered to the approximated model.
In past studies, according to Francis J. M. Schmitt, Brian A. Barsky, and Wen-Hui Du, "An Adaptive Subdivision Method for Surface-Fitting from Sampled Data", Computer Graphics, Vol. 20, No. 4, August, 1986, although the shape is approximated by adhering the Bezier patch to a three-dimensional shape, there is a problem in that a general polygon is not a target.
According to Greg Turk, "Re-Tiling Polygonal Surface", Computer Graphics, Vol. 26, No. 2, July, 1992, a trial of hierarchically approximating a polygon model is executed. There is, however, a problem in that A.lthough the algorithm in the above paper can be applied to a round shape, it is not suitable for a square shape and a general shape is not a target. Further, it is not considered to approximate the shape on the basis of characteristic points of the object shape.
Further, according to Hugues Hoppe et al., "Mesh Optimization", Computer Graphics Proceedings, Annual Conference Series, SIGGRAPH 1993, a model is approximated in a manner such that an energy is introduced to an evaluation of the approximated model, and operations for removing the edge, dividing the patch, and swapping the edge are repeated so as to minimize the energy. According to the method of the paper, however, it is necessary to execute a long repetitive calculation until the minimum point of the energy is found out. In addition, a solving method such as a simulated annealing or the like is necessary in a manner similar to other energy minimizing problems so as not to reach a local minimum point. There is no guarantee that the energy minimum point is always visually the best point.
Further, in those papers, no consideration is made up to the texture adhered to the model upon approximation. Consequently, the method of approximating the model according to the methods in the papers has a problem in that double processes are required in which the texture is newly adhered to the approximated model after the approximation.
As mentioned above, the past studies have problems regarding the approximation of a model when a polygon is drawn. That is, the conventional method has problems such that application of the shape approximation is limited, a long calculation time is necessary for approximation, and the approximation in which generally-needed characteristic points are considered is not executed. The approximation of figure data to realize a switching of continuous layers, in which the sense of incongruity to be given to the observer at the time of the switching of the approximated model is considered, is not executed.
When the approximation is executed to the geometric model to which the texture is adhered, there is a problem in that a measure to prevent a quality deterioration after the approximation, by keeping the shape of the texture adhered to the model, is not taken. There is also a problem in that a measure to eliminate the necessity to newly adhere the texture after the approximation is not taken. Further, there is a problem that the approximation in which the existence of the texture itself is considered is not executed.